package com.lfg.leetcode.leetcode200;

import com.alibaba.fastjson.JSON;

public class HeapSort {

    public static void main(String[] args){
        int nums[] = new int[]{1,2,3,4,5,6,7,8};
        sort(nums);
        System.out.println(JSON.toJSONString(nums));
    }

    public static void sort(int nums[]) {
        for (int i = (nums.length-1) / 2; i >= 0; i--) {
            shitUp(nums, i);
        }
    }

    private static void shitUp(int[] nums, int k) {
        for (int index = 2 * k + 1; index >0; ) {
            if (index < nums.length-1 && nums[index] < nums[index + 1]) {
                index++;
            }
            if (nums[index] > nums[k]) {
                swap(nums, index, k);
            }
            if(k == 0){
                break;
            }
            k = k / 2;
            index = 2 * k + 1;
        }
    }

    public static void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
